#include <iostream>
#include <string>
using namespace std;

template<class T>
class listNode
{
public:
    listNode()
    { next = NULL; } //initialing
    T zidata; //value
    listNode* next;  // pointer to next node
};

template<class T>
class linkedList
{
private:
    int listlength;
    listNode<T>* node;   //temporary node
    listNode<T>* lastnode;  // last node
    listNode<T>* headnode;  //head node
public:
    linkedList(); // int length(); //number of element
    void add(T x); //add a node from back
    void traversal(); //traverse all node and display their data
    bool isEmpty(); //determine whether the linked list is empty or not
    void Delete(T x); //delete a node whose data is x
    void insert(T x, listNode<T>* p); //Insert a node with data x after specified node p
    void insertHead(T x); //insert a node with data x from head
};

template<class T>
linkedList<T>::linkedList()
{
    this->listlength=0;
    this->node=NULL;
    this->lastnode=NULL;
    this->headnode=NULL;
}

template<class T>
void linkedList<T>::add(T x)
{
    if(this->headnode==NULL)
    {
        this->headnode=new listNode<T>;
        this->headnode->zidata=x;
        this->lastnode=this->headnode;
    }
    else
    {
        this->lastnode->next=new listNode<T>;
        this->lastnode=this->lastnode->next;
        this->lastnode->zidata=x;
    }
    this->listlength++;
}

template<class T>
void linkedList<T>::traversal()
{
    for(this->node=this->headnode; this->node!=NULL; this->node=this->node->next)
        cout<<this->node->zidata<<endl;
}

template<class T>
bool linkedList<T>::isEmpty()
{
    return this->listlength==0;
}

template<class T>
void linkedList<T>::Delete(T x)
{
    listNode<T>* l=NULL; //记录遍历到的前一个节点
    for(this->node=this->headnode; this->node!=NULL; this->node=this->node->next)
    {
        if(this->node->zidata==x)
        {
            if(this->node==this->headnode)
            {
                this->headnode=this->headnode->next;
            }
            else if(this->node==this->lastnode)
            {
                this->lastnode=l;
                this->lastnode->next=NULL;
            }
            else
            {
                l->next=this->node->next;
            }
            delete this->node;
            this->listlength--;
        }
        l=this->node;
    }
}

template<class T>
void linkedList<T>::insert(T x, listNode<T>* p)
{
    listNode<T>* oldNext=p->next;
    p->next=new listNode<T>;
    p->next->zidata=x;
    p->next->next=oldNext;
    this->listlength++;
}

template<class T>
void linkedList<T>::insertHead(T x)
{
    if(this->headnode==NULL)
    {
        this->headnode=new listNode<T>;
        this->headnode->zidata=x;
        this->lastnode=this->headnode;
    }
    else
    {
        listNode<T>* oldHead=this->headnode;
        this->headnode=new listNode<T>;
        this->headnode->zidata=x;
        headnode->next=oldHead;
    }
    this->listlength++;
}

int main()
{
    linkedList<string> ll;
    cout<<ll.isEmpty()<<endl;
    ll.add("1");
    ll.add("2");
    ll.add("3");
    cout<<ll.isEmpty()<<endl;
    ll.traversal();
    cout<<"delete:"<<endl;
    ll.Delete("2");
    ll.traversal();
    cout<<"delete Head:"<<endl;
    ll.Delete("1");
    ll.traversal();
    cout<<"delete Last:"<<endl;
    ll.Delete("3");
    ll.traversal();
    cout<<"insertHead:"<<endl;
    ll.insertHead("0");
    ll.traversal();
}
